'''
https://leetcode.cn/problems/linked-list-cycle-ii/
'''
from typing import Optional

from c03_list.utils import ListNode


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next or not head.next.next:
            return None
        s, f = head.next, head.next.next
        while f.next and f.next.next and s != f:
            s = s.next
            f = f.next.next
        if s != f:  # 没有相遇，而是走到了None =》 无环
            return None
        f = head
        while s != f:
            s = s.next
            f = f.next
        return s

